/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/min-stack
   @Language: C++
   @Datetime: 19-11-21 13:45
   */

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

// Time O(n), Space O(n)
class MinStack {
	stack<pair<int,int> > s;    // data, min
public:
	/** initialize your data structure here. */
	MinStack() {

	}

	void push(int x) {
		if(s.size()<1) s.push({x,x});
		else s.push({x,min(s.top().second,x)});
	}

	void pop() {
		if(s.size()<1) return;
		s.pop();
	}

	int top() {
		if(s.size()<1) return 0;
		return s.top().first;
	}

	int getMin() {
		if(s.size()<1) return 0;
		return s.top().second;
	}
};

